#include <bits/stdc++.h>

using namespace std;

// 复制带随机指针的链表
// 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/

// 不需要提交这个类
class Node 
{
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) 
    {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

// 提交这个类即可
// 不使用容器的做法
class Solution 
{
public:
    Node* copyRandomList(Node* head) 
    {
        if(!head) return head;

        Node *cur = head, *next = nullptr, *newNode = nullptr;
        // 1. 克隆节点连接在原节点的后面
        // 1 -> 2 -> 3 -> ...
		// 变成 : 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> ...
        while(cur)
        {
            newNode = new Node(cur->val);
            next = cur->next;
            newNode->next = next;
            cur->next = newNode;
            cur = next;
        }

        // 2. 设置克隆节点的随机指针
        // 利用上面新老节点的结构关系，设置每一个新节点的random指针
        cur = head;
        while(cur)
        {
            newNode = cur->next;
            if(cur->random) newNode->random = cur->random->next;
            cur = newNode->next;
        }

        // 3. 新老链表分离 : 老链表重新连在一起，新链表重新连在一起
        Node *newHead = new Node(0), *tail = newHead;
        cur = head;
        while(cur)
        {
            newNode = cur->next;
            next = newNode->next;
            // 尾插法构建新链表
            tail->next = newNode;
            tail = newNode;
            // 恢复老链表
            cur->next = next;
            cur = next;
        }
        
        cur = newHead->next;
        delete newHead;
        return cur;
    }
};


// 提交这个类即可
// 使用容器的做法
class Solution 
{
public:
    Node* copyRandomList(Node* head) 
    {
        if(!head) return head;

        // key : 老节点，value : 克隆出来的新节点
        unordered_map<Node*, Node*> m;
        Node* cur = head;
        while(cur)
        {
            Node* newNode = new Node(cur->val);
            m[cur] = newNode;
            cur = cur->next;
        }    

        cur = head;
        while(cur)
        {
            Node* newNode = m[cur];
            if(cur->next) newNode->next = m[cur->next];
            if(cur->random) newNode->random = m[cur->random];
            cur = cur->next;
        }
        return m[head];
    }
};